package com.javabasic.algorithm.sword_of_offer;

import com.ibm.icu.impl.Row;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [剑指 Offer 47. 礼物的最大价值](https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/)
 * @since Created by work on 2022/1/15 1:22 下午
 */
public class 剑指_Offer_47_礼物的最大价值 {

//    int[][] NEXT = new int[][]{{-1,0},{0,-1}};
//    int NEXT_LEN = 2;
//    int row, col;
//    int[][] unVisit;
//
//    public int maxValue(int[][] grid) {
//        row = grid.length;
//        col = grid[0].length;
//        if (row == 0 || col == 0) {
//            return 0;
//        }
//        return getMaxResult(grid, row-1, col-1);
//    }
//
////    private int getMaxResult(int[][] grid, int result, int row, int col) {
//////        int tempx, tempy;
//////        for (int i = 0; i < NEXT_LEN; i++) {
//////            tempx = row + NEXT[i][0];
//////            tempy = col + NEXT[i][1];
//////            if (validCoordination(tempx,tempy)) {
//////
//////            }
//////        }
////
////        if (!validCoordination(row,col)) {
////            return result;
////        }
////        unVisit[row][col] = 1;
////        return Math.max(getMaxResult(grid,result + grid[row][col],row + NEXT[0][0],col + NEXT[0][1]),
////                getMaxResult(grid,result + grid[row][col],row + NEXT[1][0],col + NEXT[1][1]));
////
////    }
//
//    private int getMaxResult(int[][] grid, int row, int col) {
//
//        if (!validCoordination(row,col)) {
//            return 0;
//        }
////        unVisit[row][col] = 1;
//        return grid[row][col] + Math.max(getMaxResult(grid,row + NEXT[0][0],col + NEXT[0][1]),
//                getMaxResult(grid,row + NEXT[1][0],col + NEXT[1][1]));
//
//    }
//
//    private boolean validCoordination(int tempx, int tempy) {
//        if (tempx < 0 || tempx >= row || tempy < 0 || tempy > col || unVisit[tempx][tempy] == 1) {
//            return false;
//        }
//        return true;
//    }



    int[][] NEXT = new int[][]{{-1,0},{0,-1}};
    int row, col;
    int[][] record;

    /**
     * 解法一：DFS+备忘录算法
     * @param grid
     * @return
     */
    public int maxValue(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        if (row == 0 || col == 0) {
            return 0;
        }
        record = new int[row][col];
        return getMaxResult(grid, row-1, col-1);
    }

    private int getMaxResult(int[][] grid, int row, int col) {

        if (!validCoordination(row,col)) {
            return 0;
        }
        if (record[row][col] > 0) {
            return record[row][col];
        }
        int temp = grid[row][col] + Math.max(getMaxResult(grid, row + NEXT[0][0], col + NEXT[0][1]),
                getMaxResult(grid, row + NEXT[1][0], col + NEXT[1][1]));
        record[row][col] = temp;
        return temp;

    }

    private boolean validCoordination(int tempx, int tempy) {
        if (tempx < 0 || tempx >= row || tempy < 0 || tempy > col) {
            return false;
        }
        return true;
    }
}
